//
// Created by Administrator on 2021/7/27.
//

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
    vector<int> vis;

public:
    void backtrack(vector<int> &nums, vector<vector<int>> &ans, int idx, vector<int> &perm) {
        if (idx == nums.size()) {
            ans.emplace_back(perm);
            return;
        }
        for (int i = 0; i < (int) nums.size(); ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.emplace_back(nums[i]);
            vis[i] = 1;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = 0;
            perm.pop_back();
        }
    }

    vector<vector<int>> permuteUnique(vector<int> &nums) {
        vector<vector<int>> ans; // 结果输出
        vector<int> perm;  // 中间结果
        vis.resize(nums.size()); // 记录
        sort(nums.begin(), nums.end());
        backtrack(nums, ans, 0, perm);
        return ans;
    }
};

class Solution2 {
    vector<int> vis;

public:
    void backtrack(string &input, vector<string> &ans, int idx, string &perm) {
        if (idx == input.size()) {
            ans.push_back(perm);
            return;
        }
        for (int i = 0; i < (int) input.size(); ++i) {
            if (vis[i] || (i > 0 && input[i] == input[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.push_back(input[i]);
            vis[i] = 1;
            backtrack(input, ans, idx + 1, perm);
            vis[i] = 0;
            perm.pop_back();
        }
    }

    vector<string> permuteUnique(string inputStr) {
        vector<string> ans; // 储存结果
        string perm;  // 中间结果
        vis.resize(inputStr.size()); // 记录表
        sort(inputStr.begin(), inputStr.end());
        backtrack(inputStr, ans, 0, perm);
        return ans;
    }
};


int main() {
    vector<int> nums{1, 2, 1};
    Solution solution;
    auto ans = solution.permuteUnique(nums);
    for (auto &row:ans) {
        for (auto &col:row) {
            cout << col;
            cout << " ";
        }
        cout << endl;
    }
    Solution2 solution2;
    auto x = solution2.permuteUnique("123412");
    for (auto &y:x) cout << y << endl;
    cout << x.size() << endl;
    return 0;
}